package algorithms.question.class44;

import common.util.MyUtil;

import java.util.HashMap;

/**
 * https://leetcode-cn.com/problems/subarrays-with-k-different-integers/
 *
 * @author guichang
 * @date 2021/10/20
 */
@SuppressWarnings("all")
public class Code1_K个不同整数的子数组_992 {

    // k-1的窗口 数种类 最左位置
    // k的窗口 数种类 最左位置
    // 窗口右移后调整上述两个窗口，调整后的最左位置相减累加
    public static void main(String[] args) {
        int[] nums = MyUtil.createArray(1, 2, 1, 2, 3);
        MyUtil.print(subarraysWithKDistinct(nums, 2));
    }

    public static int subarraysWithKDistinct(int[] nums, int k) {
        // 数组长度不可小于k
        if (nums == null || nums.length < k) {
            return 0;
        }
        int sum = 0;
        // k-1种数的窗口
        Info lessK = new Info(nums, k - 1);
        // k种数的窗口
        Info equaleK = new Info(nums, k);
        for (int i = 0; i < nums.length; i++) {
            lessK.add(i);
            equaleK.add(i);
            sum += lessK.leftIndex - equaleK.leftIndex;
        }
        return sum;
    }

    private static class Info {
        int[] nums;
        int k;
        // 词频记录
        HashMap<Integer, Integer> countMap;
        // 最左位置
        int leftIndex;

        public Info(int[] nums, int k) {
            this.nums = nums;
            this.k = k;
            countMap = new HashMap<>();
            leftIndex = 0;
        }

        /**
         * 窗口右移一位同时根据k值调整最左位置
         *
         * @param index 增加的坐标
         */
        public void add(int index) {
            int value = nums[index];
            Integer count = countMap.get(value);
            countMap.put(value, count == null ? 1 : count + 1);
            // 需要调整了
            while (countMap.keySet().size() > k) {
                int leftIndexValue = nums[leftIndex++];
                Integer num = countMap.get(leftIndexValue);
                if (num == 1) {
                    // 词频0则清除
                    countMap.remove(leftIndexValue);
                } else {
                    // 词频减1
                    countMap.put(leftIndexValue, num - 1);
                }
            }
        }
    }

}